﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using Fine.Collections.Const;
using Fine.Collections.Intf;
using Fine.Utils.Functions;
using JetBrains.Annotations;



namespace Fine.Collections.Cont
{
    public sealed class BplusMap<K,V> : WMap<K,V>
        where K: IComparable<K>
    {
        internal readonly int BlockSize;

        private static readonly Comparer<K> keyComparer = Comparer<K>.Default;
        private static readonly EqualityComparer<V> valueComparer = EqualityComparer<V>.Default;


        #region BLOCKS

        /// <summary>
        /// Abstract block.
        /// Can work with keys.
        /// </summary>
        internal abstract class Block
        {
            internal readonly int height;
            internal readonly int blockSize;

            internal InterBlock parent = null; // TODO it seems no needed
            internal int count = 0;

            internal readonly K[] keys;



            internal Block(int height, int blockSize)
            {
                this.height = height;
                this.blockSize = blockSize;
                keys = new K[blockSize];
            }


            internal int findKeyPlace(K key)
            {
                int index = Array.BinarySearch(keys, 0, count, key);
                return index >= 0 ? index : ~ index;
            }


            internal abstract void FindPath(K key, [NotNull] int[] path, out bool found);

            internal abstract void SetEntry(K key, V value, bool onlyNew, out int entryIndex, out bool noSpace, out bool entryIsNew);

            [NotNull]
            internal abstract Block BornSibling();

            [NotNull]
            internal abstract Block Bifurcate();

            internal abstract SearchResult<V> Find(K key);


            internal abstract void Exclude(K key, out bool found, out V excluded, out bool firstDeleted);

            internal abstract void Retire();


            internal K FirstKey
            {
                get { return keys[0]; }
            }

            internal K LastKey
            {
                get { return keys[count-1]; }
            }

            internal bool HasSpace()
            {
                return count < blockSize;
            }


            internal string Dump()
            {
                StringBuilder b = new StringBuilder();
                b.Append("--+ H={0} C={1} +--\n".With(height,count));
                DumpEntries(b, "    ", "    ");
                return b.ToString();
            }


            internal abstract void DumpEntries(StringBuilder buf, string prefix1, string prefix2);

            internal string DumpRange()
            {
                switch (count)
                {
                    case 0:
                        return "empty";
                    case 1:
                        return FirstKey + " (1 entry)";
                    default:
                        return "{0} .. {1} ({2} entries)".With(FirstKey.ToString(),
                                                               LastKey.ToString(), 
                                                               count);
                }
            }


            internal void VerifyKeys()
            {
                // first - verify that all keys are in order
                if (count >= 2)
                    for (int i = 0; i < count-1; i++)
                        Debug.Assert(keyComparer.Compare(keys[i],keys[i+1]) == -1, 
                                     "Disordered keys at height {0}: keys {1} and {2}.".With(height, keys[i], keys[i+1]));

                // then - verify keys of inner blocks
                VerifyKeyLinks();
            }

            internal abstract void VerifyKeyLinks();
        }


        /// <summary>
        /// Base generic block.
        /// Can work with keys and values,
        /// where value can be a pointer to an inner block (for intemediate blocks)
        /// or a user value (for terminal blocks).
        /// </summary>
        /// <typeparam name="R">type of values.</typeparam>
        internal abstract class BaseBlock<R> : Block
        {
            internal readonly R[] values;


            internal BaseBlock(int height, int blockSize)
                : base(height, blockSize)
            {
                values = new R[blockSize];
            }


            internal override Block Bifurcate()
            {
                Debug.Assert(count >= 2);
                int m = count >> 1;
                int w = count - m; // should  w == m 

                BaseBlock<R> newBlock = BornBrother();
                Array.Copy(this.keys, m, newBlock.keys, 0, w);
                Array.Copy(this.values, m, newBlock.values, 0, w);
                
                Array.Clear(this.keys, m, w);
                Array.Clear(this.values, m, w);

                this.count = m;
                newBlock.count = w;

                return newBlock;
            }


            internal override Block BornSibling()
            {
                return BornBrother();
            }


            [NotNull]
            internal abstract BaseBlock<R> BornBrother();


            internal void InsertKeyValue(K key, R value)
            {
                int index = Array.BinarySearch(keys, 0, count, key);
                if (index >= 0)
                    throw new DuplicatesFoundException("Duplicates found for key: " + key);
                index = ~index;

                InsertKeyValue(index, key, value);
            }


            internal void InsertKeyValue(int index, K key, R value)
            {
                if (index < count)
                {
                    Array.Copy(keys, index, keys, index + 1, count - index);
                    Array.Copy(values, index, values, index + 1, count - index);
                }

                keys[index] = key;
                values[index] = value;

                count++;
            }

            internal void AppendKeyValue(K key, R value)
            {
                keys[count] = key;
                values[count] = value;
                count++;
            }


            internal void DeleteEntry(int index)
            {
                DeleteAt(keys, index, count);
                DeleteAt(values, index, count);
                count--;
            }
        }


        /// <summary>
        /// Intermediate block.
        /// </summary>
        internal sealed class InterBlock : BaseBlock<Block> {

            public InterBlock(int height, int blockSize)
                : base(height, blockSize) {}


            internal override void FindPath(K key, int[] path, out bool found)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                int index = x >= 0
                                ? x
                                : x == ~0 ? 0 : (~x) - 1;
                path[height] = index;

                Debug.Assert(index >= 0);
                Debug.Assert(index < count);
                Debug.Assert(values[index] != null);

                values[index].FindPath(key, path, out found);
            }


            internal override void SetEntry(K key, V value, bool onlyNew, out int entryIndex, out bool noSpace, out bool entryIsNew)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                if (onlyNew && x >= 0)
                    throw new DuplicatesFoundException("The key ({0}) already exists.".With(key));
                int index = x > 0 ? x : x == ~0 ? 0 : ~x - 1;

                Debug.Assert(index >= 0);
                Debug.Assert(index < count);

                Block nestedBlock = values[index];
                Debug.Assert(nestedBlock != null);

                int nestedIndex;
                nestedBlock.SetEntry(key, value, onlyNew, out nestedIndex, out noSpace, out entryIsNew);
                
                if (noSpace)
                {
                    if (count < blockSize)
                    {
                        SplitNestedBlock(index);
                        Debug.Assert(index + 1 < count);
                        if (keyComparer.Compare(key, values[index + 1].keys[0]) > 0)
                            index++;
                        nestedBlock = values[index];
                        nestedBlock.SetEntry(key, value, onlyNew, out nestedIndex,
                                             out noSpace, out entryIsNew);
                    }
                    else
                    {
                        entryIndex = index;
                        return;
                    }
                }

                if (entryIsNew && nestedIndex == 0)
                {
                    if (index > 0)
                        Debug.Assert(keyComparer.Compare(keys[index - 1], key) < 0);
                    keys[index] = key;
                }

                entryIndex = index;
            }


            internal void SplitNestedBlock(int index)
            {
                Debug.Assert(count < blockSize);

                if (index < count)
                {
                    Array.Copy(keys, index, keys, index + 1, count - index);
                    Array.Copy(values, index, values, index + 1, count - index);
                }

                count++;

                Block newBlock = values[index].Bifurcate();
                keys[index + 1] = newBlock.keys[0];
                values[index + 1] = newBlock;
            }


            internal override BaseBlock<Block> BornBrother()
            {
                var newBlock = new InterBlock(height, blockSize) {parent = parent};
                return newBlock;
            }


            internal override void Exclude(K key, out bool found, out V excluded, out bool firstDeleted)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                if (x == ~0) // but it is a strange case
                {
                    found = false;
                    excluded = default(V);
                    firstDeleted = false;
                    return;
                }

                int index = x >= 0 ? x : ~x - 1;

                Block innerBlock = values[index];
                innerBlock.Exclude(key, out found, out excluded, out firstDeleted);
                
                if (innerBlock.count == 0)
                {
                    // we've deleted the last record from the inner block
                    innerBlock.Retire();
                    firstDeleted = index == 0;
                    DeleteEntry(index);
                }
                else
                {
                    if (firstDeleted)
                        keys[index] = innerBlock.FirstKey;
                    firstDeleted = false;
                }
            }


            internal override void Retire()
            {
                // nothing to do 
            }


            internal override SearchResult<V> Find(K key)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                if (x == ~0)
                    return SearchResults<V>.NotFound();
                int index = x >= 0 ? x : ~x - 1;
                return values[index].Find(key);
            }


            internal override void DumpEntries(StringBuilder buf, string prefix1, string prefix2)
            {
                for (int i = 0; i < count; i++)
                {
                    string key = keys[i].ToString() + " -> ";
                    Block innerBlock = values[i];
                    string innerPrefix1 = prefix1 + key,
                           innerPrefix2 = prefix2 + ' '.Replicate(key.Length);
                    innerBlock.DumpEntries(buf, innerPrefix1, innerPrefix2);
                }
            }


            internal override void VerifyKeyLinks()
            {
                for (int i = 0; i < count; i++)
                {
                    K key = keys[i];
                    Block innerBlock = values[i];
                    bool ok = keyComparer.Compare(key, innerBlock.FirstKey) == 0;
                    Debug.Assert(ok, "Key link broken at level {0}: key {1} points to key {2}.".With(height, key, innerBlock.FirstKey));
                }
            }
        }


        /// <summary>
        /// Terminal block.
        /// </summary>
        internal sealed class TermBlock : BaseBlock<V>
        {
            internal BplusMap<K,V> map;
            internal TermBlock prev;
            internal TermBlock next;


            internal TermBlock(BplusMap<K,V> map, int blockSize)
                : base(0, blockSize)
            {
                this.map = map;
            }


            internal V FirstValue
            {
                get { return values[0]; }
            }

            internal V LastValue
            {
                get { return values[count-1]; }
            }


            internal JumpPointer Jump(int fromIndex, K key, bool stepped = false)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                bool found = x >= 0;
                int index = found ? x : ~x;

                if (found)  // exactly found
                {
                    return new JumpPointer { block = this, index = x, result = JumpResult.Exactly };
                }
                else if (index == 0) // the required value is less than the current/from one
                {
                    return new JumpPointer { block = this, index = fromIndex, result = stepped ? JumpResult.Over : JumpResult.Before };
                }
                else if (index < count)  // not found, jumped to the nearest great one
                {
                    return new JumpPointer { block = this, index = index, result = JumpResult.Over };
                }
                else // the end reached
                {
                    if (next != null)
                        return next.Jump(0, key, true); // TODO reimplement effectively
                    else
                        return new JumpPointer { block = this, index = index, result = JumpResult.End };
                }
            }


            internal override void FindPath(K key, int[] path, out bool found)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                found = x >= 0;
                path[0] = x >= 0 ? x : ~x;
            }


            internal override void SetEntry(K key, V value, bool onlyNew, out int entryIndex, out bool noSpace, out bool entryIsNew)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                bool exists = x >= 0;

                int index = exists ? x : ~x;
                entryIndex = index;
                entryIsNew = !exists;

                if (exists)
                {
                    if (onlyNew)
                        throw new DuplicatesFoundException("The key ({0}) already exists.".With(key));

                    values[index] = value;
                    noSpace = false;
                }
                else
                {
                    noSpace = count == blockSize;
                    if (noSpace) 
                        return;

                    if (index < count)
                        InsertKeyValue(index, key, value);
                    else
                        AppendKeyValue(key, value);
                }
            }


            internal override BaseBlock<V> BornBrother()
            {
                var newBlock = new TermBlock(map, blockSize)
                               {
                                   parent = parent,
                                   prev = this,
                                   next = next
                               };
                this.next = newBlock;

                if (newBlock.next == null)
                    map.lastTerm = newBlock;

                return newBlock;
            }


            internal override void Exclude(K key, out bool found, out V excluded, out bool firstDeleted)
            {
                int index = Array.BinarySearch(keys, 0, count, key);
                found = index >= 0;
                if (!found)
                {
                    excluded = default(V);
                    firstDeleted = false;
                    return;
                }

                firstDeleted = index == 0;
                excluded = values[index];
                DeleteEntry(index);
            }


            internal override void Retire()
            {
                if (prev == null && next == null)
                    return;

                if (prev == null)
                {
                    // it is the first termblock
                    Debug.Assert(map.firstTerm == this);
                    Debug.Assert(this.next != null);
                    map.firstTerm = this.next;
                }
                else
                {
                    // it is not the first termblock
                    prev.next = this.next;
                }

                if (next == null)
                {
                    // it is the last termblock
                    Debug.Assert(map.lastTerm == this);
                    Debug.Assert(this.prev != null);
                    map.lastTerm = this.prev;
                }
                else
                {
                    // it is not the first termblock
                    next.prev = this.prev;
                }
            }


            internal override SearchResult<V> Find(K key)
            {
                int x = Array.BinarySearch(keys, 0, count, key);
                if (x < 0)
                    return SearchResults<V>.NotFound();
                return SearchResults<V>.Found(values[x]);
            }


            internal override void DumpEntries(StringBuilder buf, string prefix1, string prefix2)
            {
                for (int i = 0; i < count; i++)
                {
                    string key = keys[i].ToString();
                    string value = values[i].ToString();
                    buf.Append(i == 0 ? prefix1 : prefix2)
                       .Append(key)
                       .Append(" : ")
                       .Append(value)
                       .Append('\n');
                }
            }


            internal override void VerifyKeyLinks()
            {
                // nothing to verify here
            }
        }


        internal struct JumpPointer
        {
            internal TermBlock  block;
            internal int        index;
            internal JumpResult result;
        }


        #endregion



        #region STATE


        /// <summary>
        /// The root block of B+ tree.
        /// </summary>
        [NotNull]
        private Block root;

        /// <summary>
        /// The first terminal block.
        /// </summary>
        [NotNull]
        private TermBlock firstTerm;

        /// <summary>
        /// The last terminal block.
        /// </summary>
        [NotNull]
        private TermBlock lastTerm;

        /// <summary>
        /// Count of entries.
        /// </summary>
        private int count;


        #endregion



        #region CONSTRUCTORS

        public BplusMap(int blockSize = 32)
        {
            if (blockSize < 4)
                throw new ArgumentException(
                    "BlockSize ({0}) is too small.".With(blockSize), "blockSize");
            if (blockSize%2 != 0)
                throw new ArgumentException(
                    "BlockSize ({0}) must be even.".With(blockSize), "blockSize");
            if (blockSize > 256)
                throw new ArgumentException(
                    "BlockSize ({0}) is too large.".With(blockSize), "blockSize");

            BlockSize = blockSize;
            InitTree();

            keysView = new KeysView(this);
        }


        private void InitTree()
        {
            TermBlock initialBlock = new TermBlock(this, BlockSize);
            root = initialBlock;
            firstTerm = lastTerm = initialBlock;
            count = 0;
        }


        #endregion



        #region MODIFYING

        public void Include(K key, V value)
        {
            int index;
            bool noSpace,
                 wasNew;
            root.SetEntry(key, value, true, out index, out noSpace, out wasNew);

            if (noSpace)
            {
                GrowUp(true /*index < BlockSize*/, key);
                root.SetEntry(key, value, true, out index, out noSpace, out wasNew);
                Debug.Assert(noSpace == false);
            }

            Debug.Assert(wasNew);

            count++;
        }




        internal void GrowUp(bool bifurcate, K newKey)
        {
            var block1 = root;
            var block2 = bifurcate ? root.Bifurcate() : root.BornSibling();

            var newRoot = new InterBlock(block1.height + 1, BlockSize);
            newRoot.AppendKeyValue(block1.FirstKey, block1);
            newRoot.AppendKeyValue(bifurcate ? block2.FirstKey : newKey, block2);
            block1.parent = newRoot;
            block2.parent = newRoot;

            root = newRoot;
        }


        public V Exclude(K key)
        {
            V excluded; 

            switch (count)
            {
                case 0:
                    return default(V);

                case 1:
                    if (keyComparer.Compare(FirstKey, key) == 0)
                    {
                        excluded = firstTerm.values[0];
                        Clear();
                        return excluded;
                    }
                    else
                    {
                        return default(V);
                    }

                default:
                    bool found, firstDeleted;
                    root.Exclude(key, out found, out excluded, out firstDeleted);
                    if (found) count--;
                    return excluded;
            }
        }


        public void Clear()
        {
            InitTree();
        }



        public V this[K key]
        {
            get { return Find(key).Item; }

            set
            {
                int entryIndex;
                bool noSpace,
                     wasNew;
                root.SetEntry(key, value, false, out entryIndex, out noSpace, out wasNew);

                if (noSpace)
                {
                    GrowUp(entryIndex < BlockSize, key);
                    Include(key, value);
                    wasNew = true;
                }

                if (wasNew)
                    count++;
            }
        }


        #endregion



        #region ACCESSORS

        public SearchResult<V> Find(K key)
        {
            return root.Find(key);
        }


        public int Height
        {
            get { return root.height + 1; }
        }

        public int Count
        {
            get { return count; }
        }

        public bool IsEmpty
        {
            get { return count == 0; }
        }

        public bool IsNotEmpty
        {
            get { return count > 0; }
        }

        public K FirstKey
        {
            get
            {
                if (IsNotEmpty)
                    return firstTerm.FirstKey;
                else
                    throw new CollectionIsEmptyException();
            }
        }

        public K LastKey
        {
            get
            {
                if (IsNotEmpty)
                    return lastTerm.LastKey;
                else
                    throw new CollectionIsEmptyException();
            }
        }

        public V FirstValue
        {
            get
            {
                if (IsNotEmpty)
                    return firstTerm.FirstValue;
                else
                    throw new CollectionIsEmptyException();
            }
        }

        public V LastValue
        {
            get
            {
                if (IsNotEmpty)
                    return lastTerm.LastValue;
                else
                    throw new CollectionIsEmptyException();
            }
        }


        public bool ContainsKey(K key)
        {
            return Find(key).Found;
        }


        [NotNull]
        public SearchResult<RMapEntry<K,V>> Find(Func<K,V,bool> condition)
        {
            for (var it = TakeIterator(); it.Next();)
                if (condition(it.CurrentKey, it.CurrentValue))
                    return SearchResults<RMapEntry<K,V>>.Found(it.Current);
            return SearchResults<RMapEntry<K, V>>.NotFound();
        }


        [NotNull]
        public MapIterator TakeIterator()
        {
            return new MapIterator(this);
        }


        public ROrderSet<K> Keys
        {
            get { return keysView; }
        }

        RSet<K> RMap<K, V>.Keys
        {
            get { return keysView; }
        }

        public RList<V> Values
        {
            get { return valuesView; }
        }

        RCollection<V> RMap<K,V>.Values
        {
            get { return valuesView; }
        }

        public RCollection<RMapEntry<K, V>> Entries
        {
            get { throw new NotImplementedException(); }
        }


        public void ProcessAll([NotNull] Action<K,V> action)
        {
            TermBlock block = firstTerm;
            while (block != null)
            {
                for (int i = 0; i < block.count; i++)
                    action(block.keys[i], block.values[i]);
                block = block.next;
            }
        }


        [NotNull]
        public ConstSortMap<K,V> ToConstMap(int firstIndex = 1)
        {
            ComparableMapEntry<K,V>[] entries = new ComparableMapEntry<K,V>[count];
            int i = 0;
            ProcessAll( (k,v) => { entries[i++] = new ComparableMapEntry<K,V>(k,v); } );
            Debug.Assert(i == count);
            return new ConstSortMap<K,V>(firstIndex, entries, count, 
                                         takeOwnership: true, resort: false, removeDuplicates: false);
        }


        #endregion



        #region ITERATOR

        public abstract class BaseIterator 
        {
            [NotNull]
            internal BplusMap<K, V> map;

            [NotNull]
            internal TermBlock block;

            internal int index;
            internal bool beforeBegin;
            internal bool behindEnd;


            internal BaseIterator([NotNull] BplusMap<K, V> map)
            {
                this.map = map;
                Reset();
            }


            internal BaseIterator([NotNull] BplusMap<K, V> map, [NotNull] TermBlock block, int index, bool beforeBegin, bool behindEnd)
            {
                this.map = map;
                this.block = block;
                this.index = index;
                this.beforeBegin = beforeBegin;
                this.behindEnd = behindEnd;
            }


            public void Reset()
            {
                block = map.firstTerm;
                index = -1;
                beforeBegin = true;
                behindEnd = false;
            }


            public bool Next()
            {
                index++;
                beforeBegin = false;
                while (index >= block.count)
                {
                    if (block.next != null)
                    {
                        block = block.next;
                        index = 0;
                    }
                    else
                    {
                        behindEnd = true;
                        return false;
                    }
                }

                return true;
            }


            public JumpResult Jump(K item)
            {
                if (beforeBegin)
                    Next();
                var jr = block.Jump(index, item);
                block = jr.block;
                index = jr.index;
                return jr.result;
            }


            protected void CheckState()
            {
                if (beforeBegin) throw new OutOfCollectionException("Not iterated yet.");
                if (behindEnd) throw new OutOfCollectionException("The end of collection is reached.");
            }


            public void Dispose()
            {}
        }



        /// <summary>
        /// Map iterator. Iterates thru map entries.
        /// </summary>
        public sealed class MapIterator : BaseIterator, RMapIterator<K,V>
        {
            internal MapIterator([NotNull] BplusMap<K, V> map)
                : base(map)
            {}


            private MapIterator([NotNull] BplusMap<K, V> map, [NotNull] TermBlock block, int index, bool beforeBegin, bool behindEnd)
                : base(map, block, index, beforeBegin, behindEnd)
            {}


            public K CurrentKey
            {
                get
                {
                    CheckState();
                    return block.keys[index];
                }
            }


            public V CurrentValue
            {
                get
                {
                    CheckState();
                    return block.values[index];
                }
            }

            public RMapEntry<K,V> Current
            {
                get
                {
                    CheckState();
                    return new MapEntry<K,V>(block.keys[index], block.values[index]);
                }
            }

            public RIterator<RMapEntry<K, V>> Clone()
            {
                return new MapIterator(map, block, index, beforeBegin, behindEnd);
            }
        }


        internal sealed class KeysIterator : BaseIterator, 
                                             ROrderIterator<K>, IEnumerator<K>
        {
            public KeysIterator([NotNull] BplusMap<K,V> map)
                : base (map)
            {}


            public KeysIterator([NotNull] BplusMap<K,V> map, [NotNull] TermBlock block, int index, bool beforeBegin, bool behindEnd)
                : base(map, block, index, beforeBegin, behindEnd) 
            {}


            public K Current
            {
                get
                {
                    CheckState();
                    return block.keys[index];
                }
            }

            object IEnumerator.Current
            {
                get { return Current; }
            }

            bool IEnumerator.MoveNext()
            {
                return Next();
            }

            public RIterator<K> Clone()
            {
                return new KeysIterator(map, block, index, beforeBegin, behindEnd);
            }
        }


        internal sealed class ValuesIterator : BaseIterator, 
                                               RIterator<V>, IEnumerator<V>
        {
            public ValuesIterator([NotNull] BplusMap<K,V> map)
                : base (map)
            {}


            public ValuesIterator([NotNull] BplusMap<K,V> map, [NotNull] TermBlock block, int index, bool beforeBegin, bool behindEnd)
                : base(map, block, index, beforeBegin, behindEnd) 
            {}


            public V Current
            {
                get
                {
                    CheckState();
                    return block.values[index];
                }
            }

            object IEnumerator.Current
            {
                get { return Current; }
            }

            bool IEnumerator.MoveNext()
            {
                return Next();
            }

            public RIterator<V> Clone()
            {
                return new ValuesIterator(map, block, index, beforeBegin, behindEnd);
            }
        }


        #endregion



        #region VIEWERS


        [NotNull]
        private readonly KeysView keysView;

        internal sealed class KeysView : ROrderSet<K>
        {
            [NotNull]
            private readonly BplusMap<K, V> map;

            internal KeysView([NotNull] BplusMap<K, V> map)
            {
                this.map = map;
            }


            public int Count { get { return map.count; } }
            public bool IsEmpty { get { return map.IsEmpty; } }
            public bool IsNotEmpty { get { return map.IsNotEmpty; } }

            public K First { get { return map.FirstKey; } }
            public K Last { get { return map.LastKey; } }

            public bool Contains(K item)
            {
                return map.ContainsKey(item);
            }

            public SearchResult<K> Find(Predicate<K> predicate)
            {
                var it = map.TakeIterator();
                while (it.Next())
                    if (predicate(it.CurrentKey))
                        return SearchResults<K>.Found(it.CurrentKey);
                return SearchResults<K>.NotFound();
            }

            public K this[Predicate<K> predicate]
            {
                get { return Find(predicate).Item; }
            }

            public ROrderIterator<K> TakeIterator()
            {
                return new KeysIterator(map);
            }


            RIterator<K> RCollection<K>.TakeIterator()
            {
                return new KeysIterator(map);
            }


            IEnumerator IEnumerable.GetEnumerator()
            {
                return new KeysIterator(map);
            }

            public IEnumerator<K> GetEnumerator()
            {
                return new KeysIterator(map);
            }

            public void ProcessAll(Action<K> action)
            {
                map.ProcessAll((k,v) => action(k));
            }
        }


        [NotNull]
        private readonly ValuesView valuesView;

        internal sealed class ValuesView : RList<V>
        {
            [NotNull]
            private readonly BplusMap<K,V> map;

            internal ValuesView([NotNull] BplusMap<K,V> map)
            {
                this.map = map;
            }


            public int Count { get { return map.count; } }
            public bool IsEmpty { get { return map.IsEmpty; } }
            public bool IsNotEmpty { get { return map.IsNotEmpty; } }

            public V First { get { return map.FirstValue; } }
            public V Last { get { return map.LastValue; } }

            public bool Contains(V item)
            {
                return map.Find((k,v) => valueComparer.Equals(v,item)).Found;
            }

            public SearchResult<V> Find(Predicate<V> predicate)
            {
                var r = map.Find((k,v) => predicate(v));
                return r.Found ? SearchResults<V>.Found(r.Item.Value) : SearchResults<V>.NotFound();
            }

            public V this[Predicate<V> predicate]
            {
                get { return Find(predicate).Item; }
            }

            public RIterator<V> TakeIterator()
            {
                return new ValuesIterator(map);
            }


            RIterator<V> RCollection<V>.TakeIterator()
            {
                return new ValuesIterator(map);
            }


            IEnumerator IEnumerable.GetEnumerator()
            {
                return new ValuesIterator(map);
            }

            public IEnumerator<V> GetEnumerator()
            {
                return new ValuesIterator(map);
            }

            public void ProcessAll(Action<V> action)
            {
                map.ProcessAll((k,v) => action(v));
            }
        }

        #endregion



        #region DEBUG FUNCTIONS

        internal Block Root
        {
            get { return root; }
        }

        internal TermBlock FirstTerm
        {
            get { return firstTerm; }
        }

        internal TermBlock LastTerm
        {
            get { return lastTerm; }
        }


        internal string Dump()
        {
            StringBuilder buf = new StringBuilder();
            buf.AppendFormat("C:{0}  H:{1}\n", count, Height);
            root.DumpEntries(buf, string.Empty, string.Empty);
            return buf.ToString();
        }


        [NotNull]
        internal K[] KeysArray()
        {
            K[] keys = new K[count];
            int i = 0;
            ProcessAll( (k,v) => keys[i++] = k );
            Debug.Assert(i == count);
            return keys;
        }

        [NotNull]
        internal V[] ValuesArray()
        {
            V[] values = new V[count];
            int i = 0;
            ProcessAll( (k,v) => values[i++] = v );
            Debug.Assert(i == count);
            return values;
        }


        internal void VerifyInternalState()
        {
            // chain of terminal blocks
            for (var b = firstTerm; b != lastTerm; b = b.next) Debug.Assert(b.map == this);
            for (var b = lastTerm; b != firstTerm; b = b.prev) Debug.Assert(b.map == this);
            Debug.Assert(firstTerm.prev == null);
            Debug.Assert(lastTerm.next == null);

            // count
            int n = 0;
            ProcessAll((k,v) => n++);
            Debug.Assert(n == count, "The count variable = {0} but conted entries is {1}.".With(count,n));

            // keys
            root.VerifyKeys();
        }

        #endregion



        #region UTILITY FUNCTIONS

        internal static void DeleteAt<T>(T[] array, int index, int count)
        {
            Debug.Assert(count > 0);
            Debug.Assert(index < count);

            if (index < count-1)
                Array.Copy(array, index+1, array, index, count-index-1);
            array[count - 1] = default(T);
        }

        #endregion



    }
}
